Client cryptographic puzzles, or more simply “puzzles,” have been proposed as a mechanism to defend against resource exhaustion Denial of Service (DoS) attacks in network protocols, such as key exchange protocols. Cryptographic puzzles counterbalance computational usage between client and server machines. The client receives a cryptographic puzzle and is forced to perform computations to solve the puzzle before the client can successfully utilize resources on the server. The server ensures that the client spends sufficient resources before the server commits resources to serving requests from the client. In particular, an adversary who wishes to attack a server with connection requests will have to solve a large number of puzzles. Cryptographic puzzles have been used in computer networks to reduce or eliminate junk emails (i.e. spam), and to mitigate the effects of Denial-of-Service (DoS) attacks in network protocols.
In general, cryptographic puzzles have a high computational solution cost, are stateless, have a low computational generation cost, have a low computational solution verification cost, and have flexible puzzle complexity to mitigate DoS attacks with different levels of sophistication. The computational cost to solve a puzzle for a client should be much higher than the computational cost to generate the puzzle and verify the correctness of a puzzle solution for a defending server. The puzzles must be stateless, meaning that no clients/attackers are able to predict the puzzles that are received from a defending server. Thus, clients and attackers are unable to compute puzzle solutions in advance. While solving a puzzle includes sufficient computational complexity to reduce the rate of requests for the clients and potential attackers, the generation of a puzzle should be computationally inexpensive for the defending server. Complying with this requirement prevents the process of puzzle construction from becoming a new target of DoS attacks. In such attacks, a malicious client may flood a defending server with a large amount of initial connection requests from spoofed addresses to deceive the server into consuming considerable resource for puzzle construction. An attack scenario can be imagined in which an attacker sends a large number of bogus solutions to a defending server in order to exhaust resources on the server by performing the verification process. If the cost of puzzle verification on the server is much more expensive than that of generating random solutions on a client, the verification process is definitely possible to be another DoS attack target. Additionally, the complexity of the puzzles is adjusted flexibly according to the strength of an attack.
Various types of cryptographic puzzles are known to the art that satisfy some or all of the above properties. A representative example of such cryptographic puzzles is a hash-based reversal puzzle. In a hash-based reversal puzzle, the server constructs cryptographic puzzles using a hash function. The clients need to calculate a reverse one-way hash value of the puzzle. In this technique, the server is able to adjust the difficulty level of the cryptographic puzzle by increasing or decreasing the number of hidden bits of the pre-image sent to clients in the puzzle. The pre-image bits are bits of the original data that the server hashes to generate the puzzle. The full pre-image is the solution to the puzzle, and the server reduces or increases the computational complexity of the puzzle by increasing or reducing, respectively, the number of bits in the pre-image that the client receives with the puzzle. The client performs a brute-force search to find missing bits of pre-image whose output is given by hashing each pattern until matching the answer. To verify the solution, the server needs to perform only a single hash operation. In another puzzle scheme that is known to the art, the puzzle generation requires only a single hash. Given part of the pre-image and the length (n) of zero bits at the beginning of the hashed output, the client performs a brute-force search to find a matching solution.
FIG. 1 depicts a prior-art client-puzzle framework that implements the traditional client-puzzle mechanisms that are described above. In FIG. 1, the client first initiates the mechanism by sending a service request to the server. The server generates a puzzle using a function x←PuzzleGen(ts, validity_time, difficulty, k, ID). This function generally takes a timestamp ts denoting when the puzzle is generated and transmitted, a validity_time information stating how long the puzzle will remain valid, a difficulty parameter, a private key k and the identity of the server ID as the input. It returns a cryptographic puzzle x satisfying the desirable properties described above (hash-based reversal or other types of cryptographic puzzles may satisfy these properties). Note that for notational simplicity, FIG. 1 depicts function interfaces without including all of their input or output parameters as required (e.g., x←PuzzleGen(.) or only PuzzleGen(.)). The client solves the puzzle by executing a transformation x′←PuzzleSolve(x, difficulty, ID). Function PuzzleSolve(.) depends on the type of puzzle construction (e.g., hash-based, Diffie-Hellman (DH) based, squaring based, etc.). The client must send x′ to the server before the puzzle expires. The server receives the solution x′ from the client on time T and verifies the correctness of the solution with a function {0,1}←PuzzleVer(x′, T, validity_time, difficulty, k, ID). That is, if the puzzle solution x′ is valid and solved within a designated time interval, PuzzleVer(.) returns 1 meaning valid; otherwise, it returns 0 meaning invalid. The server allocates the resource for the client if PuzzleVer(.) returns 1.
As described above, the existing cryptographic puzzle systems require the client to contact the server to receive a puzzle. In some networked systems, the requirement for a server to transmit the puzzle to the client immediately before the client establishes a network communication session with the server leads to unacceptable increases in network latency and operating overhead. Puzzles, however, are still useful in mitigating denial of service attacks. Consequently, improvements to network systems that provide greater flexibility to network communication while mitigating denial of service attacks would be beneficial.